#!/usr/bin/python3
import math

try:
    t = int(input())
    ids = 1
    while t > 0:
        n, m = map(int, input().split())
        print(f"Case #{ids}: {int(n*m//math.gcd(n,m)/m)}")
        t = t - 1
        ids = ids + 1

except ValueError:
    pass
except EOFError:
    pass
except MemoryError:
    pass
